/**
 * 221. 最大正方形
 * https://leetcode-cn.com/problems/maximal-square/
 */

// /**
//  * @param {number[]} heights
//  * @return {number}
//  */
// function maximalSquareInHistogram(heights) {
//   let max = 0;
//   for (let i = heights.length - 1; i >= 0; i -= 1) {
//     let height = heights[i];
//     if (height < 1) {
//       continue;
//     }
//     let furthest = i - height + 1;
//     for (let j = i; j >= furthest; j -= 1) {
//       if (j < 0) {
//         furthest = 0;
//         break;
//       }
//       if (heights[j] < height) {
//         furthest += (height - heights[j]);
//         height = heights[j];
//       }
//     }
//     const size = i - furthest + 1;
//     max = Math.max(max, size * size);
//   }
//   return max;
// }
//
// /**
//  * 柱状图
//  * @param {string[][]} matrix
//  * @return {number}
//  */
// function maximalSquare(matrix) {
//   const { length: n } = matrix;
//   const { length: m } = matrix[0];
//   for (let j = 0; j < m; j += 1) {
//     if (matrix[0][j] === '0') {
//       matrix[0][j] = 0;
//     } else {
//       matrix[0][j] = 1;
//     }
//   }
//   for (let i = 1; i < n; i += 1) {
//     for (let j = 0; j < m; j += 1) {
//       if (matrix[i][j] === '0') {
//         matrix[i][j] = 0;
//       } else {
//         matrix[i][j] = matrix[i - 1][j] + 1;
//       }
//     }
//   }
//   let max = 0;
//   for (let i = 0; i < n; i += 1) {
//     const area = maximalSquareInHistogram(matrix[i]);
//     if (area > max) {
//       max = area;
//     }
//   }
//   return max;
// }

/**
 * 动态规划
 * @param {string[][]} matrix
 * @return {number}
 */
function maximalSquare(matrix) {
  const { length: n } = matrix;
  const { length: m } = matrix[0];
  let max = 0;
  for (let i = 0; i < n; i += 1) {
    if (matrix[i][0] === '0') {
      matrix[i][0] = 0;
    } else {
      matrix[i][0] = 1;
      max = 1;
    }
  }
  for (let j = 1; j < m; j += 1) {
    if (matrix[0][j] === '0') {
      matrix[0][j] = 0;
    } else {
      matrix[0][j] = 1;
      max = 1;
    }
  }
  for (let i = 1; i < n; i += 1) {
    for (let j = 1; j < m; j += 1) {
      if (matrix[i][j] === '0') {
        matrix[i][j] = 0;
      } else {
        matrix[i][j] = Math.min(matrix[i - 1][j], matrix[i][j - 1], matrix[i - 1][j - 1]) + 1;
        max = Math.max(matrix[i][j], max);
      }
    }
  }
  return max * max;
}

console.log(maximalSquare([
  ['1', '0', '1', '0', '0'],
  ['1', '0', '1', '1', '1'],
  ['1', '1', '1', '1', '1'],
  ['1', '0', '0', '1', '0'],
]) === 4);
console.log(maximalSquare([
  ['1', '0'],
  ['0', '1'],
]) === 1);
console.log(maximalSquare([
  ['0'],
]) === 0);
console.log(maximalSquare([
  ['0', '0', '0', '1'],
  ['1', '1', '0', '1'],
  ['1', '1', '1', '1'],
  ['0', '1', '1', '1'],
  ['0', '1', '1', '1'],
]) === 9);
